#define _CRT_SECURE_NO_WARNINGS 1

#include "BT.h"

BTN* BuyNewNode(BTDT val)
{
	BTN* newnode = (BTN*)malloc(sizeof(BTN));
	if (newnode == NULL)
	{
		printf("BuyNewNode malloc fail");
		return NULL;
	}

	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTN* CreateBinaryTree()
{
	BTN* node1 = BuyNewNode(1);
	BTN* node2 = BuyNewNode(2);
	BTN* node3 = BuyNewNode(3);
	BTN* node4 = BuyNewNode(4);
	BTN* node5 = BuyNewNode(5);
	BTN* node6 = BuyNewNode(6);
	BTN* node7 = BuyNewNode(7);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;

	return node1;
}

void PrevOrder(BTN* root)
{
	if (root == NULL)
	{
		return;
	}
	
	printf("%d ", root->val);

	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTN* root)
{
	if (root == NULL)
	{
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

void PostOrder(BTN* root)
{
	if (root == NULL)
	{
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

int BTSize(BTN* root)
{
	return root == NULL ? 0 : BTSize(root->left) + BTSize(root->right) + 1;
}

int BTLeafSize(BTN* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BTLeafSize(root->left) + BTLeafSize(root->right);
	}
}

int BTHeight(BTN* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int left = BTHeight(root->left);
	int right = BTHeight(root->right);

	return left > right ? left + 1 : right + 1;
}

int BTLevelSize(BTN* root, int k)
{
	assert(k > 0);
	
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BTLevelSize(root->left, k - 1) + BTLevelSize(root->right, k - 1);
}